package puzzle.projecteuler.p300;

import java.util.ArrayList;
import java.util.List;




public class Problem225C {
	

	/**
	 * 注意 T_n mod m是周期数列，周期不大于m^3 
	 * 
	 * answer	: 2009
	 * time cost: 31 ms
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
	
		long s = System.currentTimeMillis();

		List<Integer> cache = new ArrayList<Integer>();
		int m = 1;
		while (cache.size() < 124) {
			boolean exists = false;
			for (Integer t: cache) {
				if (m % t == 0) {
					exists = true;
				}
			}
			if (exists || getDivisorIndex(m) == -1) {
				cache.add(m);
			}
			m += 2;
		}
		int index = cache.size();
		System.out.println(cache.size() + ": " + cache.get(index-1));
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
	
	/**
	 * 获得 T_n % m = 0的最小n。找不到，就返回-1。
	 * @param m
	 * @return
	 */
	private static int getDivisorIndex(int m) {
		
		int index = 3;
		int t1 = 1, t2 = 1, t3 = 1;
		for (long i = 0; i <= (long)m*m*m; i ++) {
			int t = t1;
			t1 = t2;
			t2 = t3;
			t3 = (t + t1 + t2) % m;
			index ++;
			if (t3 == 0) {
				return index; 
			} else if (t3 == 1 && t2 == 1 && t1 == 1) {
				return -1;
			}
		}
		return -1;
	}
}
